package algorithm.dynamicProgramming;
//题目：有三种硬币，面值2.5.7，买一本书需要27元，如何用最少的硬币整好付清。

public class CoinQuestion {
    public static void main(String[] args) {
        int[] coin = {2,5,7};
        System.out.println(nums(coin, 27));

    }
    public static int nums(int[] coin,int monkey){
        int[] f = new int[monkey+1];  //因为会用到monkey这个下标

        //初始化
        f[0] = 0;  //第一个0代表钱，等号后面的0代表硬币个数

        for (int i = 1;i<monkey+1;i++){
            f[i] = Integer.MAX_VALUE;//先给每一个钱对应的硬币数都赋值为无穷大
            for (int j =0;j<coin.length;j++){
                if (i>=coin[j] && f[i-coin[j]]!=Integer.MAX_VALUE){
                    f[i] = Math.min(f[i],f[i-coin[j]]+1);
                }

            }
        }
        if (f[monkey]==Integer.MAX_VALUE){
            return -1;
        }
        return f[monkey];

    }
}
